// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package strconv

import (
	"math/bits"
)

// 使用Ryū算法进行二进制到十进制的转换。
// 
// 参见Ulf Adams，“Ryū：快速浮点到字符串转换”（doi:10.1145/3192366.3192369）
// 
// 固定精度格式是原稿
// 算法的一个变体，其中需要10^k的单次乘法，

// RyuftoAffixed32格式的mant*（2^exp）和prec十进制数字。
func ryuFtoaFixed32(d *decimalSlice, mant uint32, exp int, prec int) {
	if prec < 0 {
		panic("ryuFtoaFixed32 called with negative prec")
	}
	if prec > 9 {
		panic("ryuFtoaFixed32 called with prec > 9")
	}
	// 零输入。
	if mant == 0 {
		d.nd, d.dp = 0, 0
		return
	}
	// 重新规范化为25位尾数。
	e2 := exp
	if b := bits.Len32(mant); b < 25 {
		mant <<= uint(25 - b)
		e2 += int(b) - 25
	}
	// 选择一个指数，使四舍五入的mant*（2^e2）*（10^q）至少有prec十进制数字，即
	// mant*（2^e2）*（10^q）>=10^（prec-1）
	// 因为mant>=2^24，选择就足够了：
	// 2^（e2+24）>=10^（-q+prec-1）
	// 或q=-mulByLog2Log10（e2+24）+prec-1 
	q := -mulByLog2Log10(e2+24) + prec - 1

	// 现在计算mant*（2^e2）*（10^q）。
	// 这是一个精确的计算吗？
	// 只有10的小正幂是精确的（5^28有66位）。
	exact := q <= 27 && q >= 0

	di, dexp2, d0 := mult64bitPow10(mant, e2, q)
	if dexp2 >= 0 {
		panic("not enough significant bits after mult64bitPow10")
	}
	// 作为一种特殊情况，如果指数
	// 为负，并且如果它相当于计算一个精确的除法，那么计算可能仍然是精确的。在这种情况下，我们忽略所有的低位。
	// 注意，10^11的除法不能精确，因为5^11有26位。
	if q < 0 && q >= -10 && divisibleByPower5(uint64(mant), -q) {
		exact = true
		d0 = true
	}
	// 删除额外的低位并保留舍入信息。
	extra := uint(-dexp2)
	extraMask := uint32(1<<extra - 1)

	di, dfrac := di>>extra, di&extraMask
	roundUp := false
	if exact {
		// 如果我们计算出一个精确的乘积，d+1/2 
		// 如果'd'是奇数，则应该四舍五入到d+1。否则，d+1/2总是四舍五入，因为我们在下面截短了。
		roundUp = dfrac > 1<<(extra-1) ||
			(dfrac == 1<<(extra-1) && !d0) ||
			(dfrac == 1<<(extra-1) && d0 && di&1 == 1)
	} else {
		roundUp = dfrac>>(extra-1) == 1
	}
	if dfrac != 0 {
		d0 = false
	}
	// 继续执行请求的位数
	formatDecimal(d, uint64(di), !d0, roundUp, prec)
	// 调整指数
	d.dp -= q
}

// RyuftoFixed64格式mant*（2^exp）和预十进制数字。
func ryuFtoaFixed64(d *decimalSlice, mant uint64, exp int, prec int) {
	if prec > 18 {
		panic("ryuFtoaFixed64 called with prec > 18")
	}
	// 零输入。
	if mant == 0 {
		d.nd, d.dp = 0, 0
		return
	}
	// 重新规范化为55位尾数。
	e2 := exp
	if b := bits.Len64(mant); b < 55 {
		mant = mant << uint(55-b)
		e2 += int(b) - 55
	}
	// 选择一个指数，使四舍五入的mant*（2^e2）*（10^q）至少有prec十进制数字，即
	// mant*（2^e2）*（10^q）>=10^（prec-1）
	// 因为mant>=2^54，选择就足够了：
	// 2^（e2+54）>=10^（-q+prec-1）
	// 或q=-mulByLog2Log10（e2+54）+prec-1 
	// 
	// 所需的最小指数是-mulByLog2Log10（1025）+18=-291 
	// 所需的最大指数是mulByLog2Log10（1074=342 
	q := -mulByLog2Log10(e2+54) + prec - 1

	// 这是一个精确的计算吗？
	// 只有10的小正幂是精确的（5^55有128位）。
	exact := q <= 55 && q >= 0

	di, dexp2, d0 := mult128bitPow10(mant, e2, q)
	if dexp2 >= 0 {
		panic("not enough significant bits after mult128bitPow10")
	}
	// 作为一种特殊情况，如果指数
	// 为负，并且如果它相当于计算一个精确的除法，那么计算可能仍然是精确的。在这种情况下，我们忽略所有的低位。
	// 注意，10^23的除法不能精确，因为5^23有54位。
	if q < 0 && q >= -22 && divisibleByPower5(mant, -q) {
		exact = true
		d0 = true
	}
	// 删除额外的低位并保留舍入信息。
	extra := uint(-dexp2)
	extraMask := uint64(1<<extra - 1)

	di, dfrac := di>>extra, di&extraMask
	roundUp := false
	if exact {
		// 如果我们计算出一个精确的乘积，如果“d”是奇数，d+1/2应该四舍五入到d+1。否则，d+1/2总是四舍五入，因为我们在下面截断了。
		roundUp = dfrac > 1<<(extra-1) ||
			(dfrac == 1<<(extra-1) && !d0) ||
			(dfrac == 1<<(extra-1) && d0 && di&1 == 1)
	} else {
		roundUp = dfrac>>(extra-1) == 1
	}
	if dfrac != 0 {
		d0 = false
	}
	// 继续执行请求的位数
	formatDecimal(d, di, !d0, roundUp, prec)
	// 调整指数
	d.dp -= q
}

var uint64pow10 = [...]uint64{
	1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
}

// 格式十进制用尾数m的最多预十进制位数
// 填充d。布尔值trunc表示与正在格式化的原始数字相比，m 
// 是否被截断。
func formatDecimal(d *decimalSlice, m uint64, trunc bool, roundUp bool, prec int) {
	max := uint64pow10[prec]
	trimmed := 0
	for m >= max {
		a, b := m/10, m%10
		m = a
		trimmed++
		if b > 5 {
			roundUp = true
		} else if b < 5 {
			roundUp = false
		} else { // b==5 
			// 如果有尾随数字，
			// 或者如果m的新值是奇数（从四舍五入到偶数约定），
			roundUp = trunc || m&1 == 1
		}
		if b != 0 {
			trunc = true
		}
	}
	if roundUp {
		m++
	}
	if m >= max {
		// 如果di最初是99999，则会发生这种情况。。。。xx 
		m /= 10
		trimmed++
	}
	// 呈现数字（类似于formatBits）
	n := uint(prec)
	d.nd = int(prec)
	v := m
	for v >= 100 {
		var v1, v2 uint64
		if v>>32 == 0 {
			v1, v2 = uint64(uint32(v)/100), uint64(uint32(v)%100)
		} else {
			v1, v2 = v/100, v%100
		}
		n -= 2
		d.d[n+1] = smallsString[2*v2+1]
		d.d[n+0] = smallsString[2*v2+0]
		v = v1
	}
	if v > 0 {
		n--
		d.d[n] = smallsString[2*v+1]
	}
	if v >= 10 {
		n--
		d.d[n] = smallsString[2*v]
	}
	for d.d[d.nd-1] == '0' {
		d.nd--
		trimmed++
	}
	d.dp = d.nd + trimmed
}

// Ryufta最短格式mant*2^exp，带预十进制数字。
func ryuFtoaShortest(d *decimalSlice, mant uint64, exp int, flt *floatInfo) {
	if mant == 0 {
		d.nd, d.dp = 0, 0
		return
	}
	// 如果输入是位小于尾数的精确整数，则
	// 上一个和下一个整数是不允许的表示形式。
	if exp <= 0 && bits.TrailingZeros64(mant) >= -exp {
		mant >>= uint(-exp)
		ryuDigits(d, mant, mant, mant, true, false)
		return
	}
	ml, mc, mu, e2 := computeBounds(mant, exp, flt)
	if e2 == 0 {
		ryuDigits(d, ml, mc, mu, true, false)
		return
	}
	// 找到大于2^-e2的10^q*我们将使用128位算法乘以10^q。
	q := mulByLog2Log10(-e2) + 1

	// 所有3个数字的指数都相同。
	var dl, dc, du uint64
	var dl0, dc0, du0 bool
	if flt == &float32info {
		var dl32, dc32, du32 uint32
		dl32, _, dl0 = mult64bitPow10(uint32(ml), e2, q)
		dc32, _, dc0 = mult64bitPow10(uint32(mc), e2, q)
		du32, e2, du0 = mult64bitPow10(uint32(mu), e2, q)
		dl, dc, du = uint64(dl32), uint64(dc32), uint64(du32)
	} else {
		dl, _, dl0 = mult128bitPow10(ml, e2, q)
		dc, _, dc0 = mult128bitPow10(mc, e2, q)
		du, e2, du0 = mult128bitPow10(mu, e2, q)
	}
	if e2 >= 0 {
		panic("not enough significant bits after mult128bitPow10")
	}
	// 这是一个精确的计算吗？
	if q > 55 {
		// 十的大正幂不是精确的
		dl0, dc0, du0 = false, false, false
	}
	if q < 0 && q >= -24 {
		// 被十的幂除法可能是精确的。
		// （请注意，5^25是一个59位的数字，所以被5^25除法永远不精确）。
		if divisibleByPower5(ml, -q) {
			dl0 = true
		}
		if divisibleByPower5(mc, -q) {
			dc0 = true
		}
		if divisibleByPower5(mu, -q) {
			du0 = true
		}
	}
	// 将结果（dl，dc，du）*2^e2表示为整数。
	// 必须删除额外的位并计算舍入提示。
	extra := uint(-e2)
	extraMask := uint64(1<<extra - 1)
	// 现在计算以10为底的整数尾数。
	dl, fracl := dl>>extra, dl&extraMask
	dc, fracc := dc>>extra, dc&extraMask
	du, fracu := du>>extra, du&extraMask
	// 因此允许使用'du'吗？
	// 当它被截断时总是允许的，但是如果它是精确的，并且原始的二进制尾数甚至是
	// 当不允许时，我们可以减去1。
	uok := !du0 || fracu > 0
	if du0 && fracu == 0 {
		uok = mant&1 == 0
	}
	if !uok {
		du--
	}
	// “dc”是正确的以10为底的四舍五入尾数吗？
	// 正确的四舍五入可能是dc+1 
	cup := false // 不要四舍五入。
	if dc0 {
		// 如果我们计算一个精确的乘积，如果'dc'是奇数，半整数
		// 应该舍入到下一个（偶数）整数。
		cup = fracc > 1<<(extra-1) ||
			(fracc == 1<<(extra-1) && dc&1 == 1)
	} else {
		// 否则，结果是理想
		// 结果的较低截断。
		cup = fracc>>(extra-1) == 1
	}
	// 是否允许使用“dl”表示？
	// 仅当它是一个精确值，且原始二进制尾数
	// 为偶数时。
	lok := dl0 && fracl == 0 && (mant&1 == 0)
	if !lok {
		dl++
	}
	// 我们需要记住'dc'的修剪数字是否为零。
	c0 := dc0 && fracc == 0
	// 呈现数字
	ryuDigits(d, dl, dc, du, c0, cup)
	d.dp -= q
}

// mulByLog2Log10返回数学。
// /中整数x的下限（x*log（2）/log（10））/范围-1600<=x和x<=+1600。
// 
// 范围限制允许我们使用更快的整数算法，而不是
// 较慢的浮点算法。正确性通过单元测试来验证。
func mulByLog2Log10(x int) int {
	// 日志（2）/log（10）≈ 0.30102999566≈ 78913/2^18 
	return (x * 78913) >> 18
}

// mulByLog10Log2返回数学。
// 范围-500<=x&&x<=500的整数x的下限（x*log（10）/log（2））。
// 
// 范围限制允许我们使用更快的整数算法，而不是
// 较慢的浮点算法。正确性通过单元测试来验证。
func mulByLog10Log2(x int) int {
	// 日志（10）/log（2）≈ 3.32192809489≈ 108853/2^15 
	return (x * 108853) >> 15
}

// computeBounds返回一个浮点向量（l，c，u）×2^e2 
// 其中尾数是55位（或26位）整数，描述由输入浮点64或浮点32表示的间隔
// 。
func computeBounds(mant uint64, exp int, flt *floatInfo) (lower, central, upper uint64, e2 int) {
	if mant != 1<<flt.mantbits || exp == flt.bias+1-int(flt.mantbits) {
		// 常规大小写（或非规范化）
		lower, central, upper = 2*mant-1, 2*mant, 2*mant+1
		e2 = exp - 1
		return
	} else {
		// 指数边界
		lower, central, upper = 4*mant-1, 4*mant, 4*mant+2
		e2 = exp - 2
		return
	}
}

func ryuDigits(d *decimalSlice, lower, central, upper uint64,
	c0, cup bool) {
	lhi, llo := divmod1e9(lower)
	chi, clo := divmod1e9(central)
	uhi, ulo := divmod1e9(upper)
	if uhi == 0 {
		// 仅低位（非规范化）
		ryuDigits32(d, llo, clo, ulo, c0, cup, 8)
	} else if lhi < uhi {
		// 一次截断9位。
		if llo != 0 {
			lhi++
		}
		c0 = c0 && clo == 0
		cup = (clo > 5e8) || (clo == 5e8 && cup)
		ryuDigits32(d, lhi, chi, uhi, c0, cup, 8)
		d.dp += 9
	} else {
		d.nd = 0
		// emit high part 
		n := uint(9)
		for v := chi; v > 0; {
			v1, v2 := v/10, v%10
			v = v1
			n--
			d.d[n] = byte(v2 + '0')
		}
		d.d = d.d[n:]
		d.nd = int(9 - n)
		// emit low part 
		ryuDigits32(d, llo, clo, ulo,
			c0, cup, d.nd+8)
	}
	// trim training zero 
	for d.nd > 0 && d.d[d.nd-1] == '0' {
		d.nd--
	}
	// trim initial zero 
	for d.nd > 0 && d.d[0] == '0' {
		d.nd--
		d.dp--
		d.d = d.d[1:]
	}
}

// ryuDigits32为小于1e9的数字发出十进制数字。
func ryuDigits32(d *decimalSlice, lower, central, upper uint32,
	c0, cup bool, endindex int) {
	if upper == 0 {
		d.dp = endindex + 1
		return
	}
	trimmed := 0
	// 记住最后一个经过修剪的数字，以检查四舍五入。
	// c0将用于记住以下数字的零度。反复计算：
	cNextDigit := 0
	for upper > 0 {
		// 。
		l := (lower + 9) / 10
		c, cdigit := central/10, central%10
		u := upper / 10
		if l > u {
			// 不要修剪最后一位数字，因为禁止低于l 
			// 其他，现在修剪并退出。
			break
		}
		// 检查我们没有越过下边界。
		// 如果l<u但c==l-1基本上是不可能的，
		// 但可能发生在以下情况：。。11 
		// 中央=。。19 
		// 上限=。。31 
		// 表示'central'非常接近，但小于
		// 一个以许多零结尾的整数，通常
		// 取整逻辑隐藏了问题。
		if l == c+1 && c < u {
			c++
			cdigit = 0
			cup = false
		}
		trimmed++
		// 还记得c的修剪数字
		c0 = c0 && cNextDigit == 0
		cNextDigit = int(cdigit)
		lower, central, upper = l, c, u
	}
	// 我们应该四舍五入吗？
	if trimmed > 0 {
		cup = cNextDigit > 5 ||
			(cNextDigit == 5 && !c0) ||
			(cNextDigit == 5 && c0 && central&1 == 1)
	}
	if central < upper && cup {
		central++
	}
	// 我们知道数字的结尾，直接填充
	endindex -= trimmed
	v := central
	n := endindex
	for n > d.nd {
		v1, v2 := v/100, v%100
		d.d[n] = smallsString[2*v2+1]
		d.d[n-1] = smallsString[2*v2+0]
		n -= 2
		v = v1
	}
	if n == d.nd {
		d.d[n] = byte(v + '0')
	}
	d.nd = endindex + 1
	d.dp = d.nd + trimmed
}

// mult64bitPow10使用25位
// 尾数进行浮点输入，并将其与10^q相乘。得到的尾数
// 是m*P>>57，其中P是DetailedPowerStories表的64位元素。
// 通常为31或32位宽。
// 如果所有修剪位均为零，则返回的布尔值为真。
// 
// 也就是说：
// m*2^e2*round（10^q）=resM*2^resE+ε
// exact=ε==0 
func mult64bitPow10(m uint32, e2, q int) (resM uint32, resE int, exact bool) {
	if q == 0 {
		// P==1<<63 
		return m << 6, e2 - 6, true
	}
	if q < detailedPowersOfTenMinExp10 || detailedPowersOfTenMaxExp10 < q {
		// 由于浮动32/浮动64指数
		panic("mult64bitPow10: power of 10 is out of range")
	}
	pow := detailedPowersOfTen[q-detailedPowersOfTenMinExp10][1]
	if q < 0 {
		pow += 1
	}
	hi, lo := bits.Mul64(uint64(m), pow)
	e2 += mulByLog10Log2(q) - 63 + 57
	return uint32(hi<<7 | lo>>57), e2, lo<<7 == 0
}

// mult128bitPow10接受一个带有55位
// 尾数的浮点输入，并将其与10^q相乘。得到的尾数
// 是m*P>>119，其中P是DetailedPowerStories表的128位元素。
// 通常为63或64位宽。
// 返回的布尔值为真，即所有修剪位均为零。
// 
// 也就是说：
// m*2^e2*round（10^q）=resM*2^resE+ε
// 精确=ε==0 
func mult128bitPow10(m uint64, e2, q int) (resM uint64, resE int, exact bool) {
	if q == 0 {
		// P==1<<127 
		return m << 8, e2 - 8, true
	}
	if q < detailedPowersOfTenMinExp10 || detailedPowersOfTenMaxExp10 < q {
		// 由于浮点32/浮点64指数
		panic("mult128bitPow10: power of 10 is out of range")
	}
	pow := detailedPowersOfTen[q-detailedPowersOfTenMinExp10]
	if q < 0 {
		// 十的逆幂必须四舍五入。
		pow[0] += 1
	}
	e2 += mulByLog10Log2(q) - 127 + 119

	// 长乘法
	l1, l0 := bits.Mul64(m, pow[0])
	h1, h0 := bits.Mul64(m, pow[1])
	mid, carry := bits.Add64(l1, h0, 0)
	h1 += carry
	return h1<<9 | mid>>55, e2, mid<<9 == 0 && l0 == 0
}

func divisibleByPower5(m uint64, k int) bool {
	if m == 0 {
		return true
	}
	for i := 0; i < k; i++ {
		if m%5 != 0 {
			return false
		}
		m /= 5
	}
	return true
}

// divmod1e9计算商和除以1e9的余数，
// 避免在32位平台上运行时uint64除法。
func divmod1e9(x uint64) (uint32, uint32) {
	if !host32bit {
		return uint32(x / 1e9), uint32(x % 1e9)
	}
	// 使用与amd64编译器相同的操作序列。
	hi, _ := bits.Mul64(x>>1, 0x89705f4136b4a598) // 1e-9 
	q := hi >> 28
	return uint32(q), uint32(x - q*1e9)
}
